package com.youth.day01;

/**
 *  冒泡排序
 * @author Jinx
 * @date 2021/6/4 8:36
 */
public class BubbleSort {


    /**
     *  分析下时间复杂度： O（n²）
     *  假设arr的长度为 n， 那么外层循环 n-1 次，执行次数相当于：
     *  第一次：n-1 次
     *  第二次：n-2 次
     *  n-1 + n-2 + n-3 + ... + 1
     *
     *
     *  暴力分析：
     *  外层i--，执行n次
     *  内层j++，执行n次（虽然会随着外层的i变化而变化，但始终都是++，可近似看作n次）
     *  最终：外层执行次数 * 内层执行次数  即是最终时间复杂度
     *
     */
    public static int[] sort(int[] arr){
        if(arr == null || arr.length < 1){
            return arr;
        }

        // 外层控制轮数  内层比较
        int temp;
        for (int i = arr.length - 1; i > 0; i--) {
            for (int j = 1; j <= i; j++) {
                if(arr[j-1] > arr[j]){
                    // 交换位置
                    temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
            }
        }

        return arr;
    }
}
